package course.p7_binaryTree.s1_NorBinaryNode;

import course.p7_binaryTree.Node;

import java.util.*;

/**
 * 普通二叉树的实现
 */
public class NorBinaryTree {

    //根节点
    private Node root;
    //树大小
    private int size;

    public NorBinaryTree() {
        this.root = new Node();
    }

    /**
     * 向树中添加节点(从上到下层次顺序添加)
     * @param data 添加的数值
     */
    public void add(int data) {
        if(root.getData()==null) {
            root.setData(data);
            size = 1;
        }
        else {
            //通过队列来辅助进行层次遍历添加元素
            Queue<Node> queue = new LinkedList<>();
            //首先存入祖宗节点，因为层次遍历中它是第一个被遍历的
            queue.add(root);
            while(!queue.isEmpty()){
                boolean isSuccess = false;
                for(int i = queue.size();i>0;i--){
                    Node node = queue.poll();
                    assert node != null;
                    if(node.getLeft()!=null) {
                        queue.add(node.getLeft());
                    }
                    else{
                        node.setLeft(new Node(data));
                        isSuccess = true;
                        break;
                    }

                    if(node.getRight()!=null) {
                        queue.add(node.getRight());
                    }
                    else{
                        node.setRight(new Node(data));
                        isSuccess = true;
                        break;
                    }
                }
                if(isSuccess) break;
            }
            size++;
        }
    }

    /**
     * 树的删除操作,删除第一个和data相等的节点
     * @param data 需要删除的值
     */
    public void delete(int data) {
        Node father = root;
        if(father.getData().equals(data)){
            root = null;
            return;
        }
        List<Node> result = new ArrayList<>();
        // 递归前序遍历
        findOneBeforeTra(data,root,result);
        if(result.size() == 0){
            System.out.println("不存在该元素： "+data);
            return;
        }
        result.get(0).setData(null);
    }

    /**
     * 将直到旧值更新为新值
     * @param oldData 旧值
     * @param newData 新值
     */
    public void update(int oldData,int newData) {
        Node first = root;
        if(first==null)  return ;
        //通过栈来辅助进行树的遍历
        Stack<Node> S = new Stack<>();
        while(true){
            while(first!=null){
                if(first.getData().equals(oldData)){
                    first.setData(newData);
                    return;
                }
                S.push(first);
                first = first.getLeft();
            }
            if(S.isEmpty()) break;
            first = S.pop();
            first = first.getRight();
        }
    }



    /**
     * 遍历方法
     * @param traverseType
     * B--前序遍历  M--中序遍历 A--后序遍历  FB--非递归前序遍历  FM--非递归中序遍历  FA--非递归后序遍历
     */
    public void traverse(String traverseType) {
        if(traverseType.equals("B")) {
            beforeTraverse(root,new ArrayList<>());
        }
        if(traverseType.equals("M")){
            middleTraverse(root,new ArrayList<>());
        }
        if(traverseType.equals("A")){
            afterTraverse(root,new ArrayList<>());
        }
        if(traverseType.equals("FB")){
            List<Integer> result = fBeforeTraverse(root);
            System.out.println();
            for(Integer num:result) System.out.print(num+" ");
        }
        if(traverseType.equals("FM")){
            Integer[] result = fMiddleTraverse(root);
            System.out.println();
            for(Integer num:result) System.out.print(num+" ");
        }
        if(traverseType.equals("FA")){
            Integer[] result = fAfterTraverse(root);
            System.out.println();
            for(Integer num:result) System.out.print(num+" ");
        }
        if(traverseType.equals("Level")){
            List<List<Integer>> result = levelOrder(root);
            for(List<Integer> item:result){
                System.out.println(item);
            }
        }
    }


    /**
     * 递归版前序遍历(根左右)
     * @param root 根节点
     */
    private void beforeTraverse(Node root,List<Integer> result) {
        if(root!=null) {
            System.out.print(root.getData()+" ");
            result.add(root.getData());
            beforeTraverse(root.getLeft(),result);
            beforeTraverse(root.getRight(),result);
        }
    }

    /**
     * 递归版中序遍历(左根右)
     * @param root
     */
    private void middleTraverse(Node root,List<Integer> result) {
        if(root!=null) {
            middleTraverse(root.getLeft(),result);
            System.out.print(root.getData()+" ");
            result.add(root.getData());
            middleTraverse((root.getRight()),result);
        }
    }

    /**
     * 递归版后序遍历二叉树（左右根）
     * @param root
     */
    private void afterTraverse(Node root,List<Integer> result) {
        if(root!=null) {
            afterTraverse(root.getLeft(),result);
            afterTraverse((root.getRight()),result);
            System.out.print(root.getData()+" ");
            result.add(root.getData());
        }
    }

    /**
     * 通过前序遍历查找元素
     * @param data
     * @return
     */
    private void findOneBeforeTra(int data,Node root,List<Node> result) {
        if(root!=null) {
            if(root.getData()==data) {
                result.add(root);
            }
            findOneBeforeTra(data,root.getLeft(),result);
            findOneBeforeTra(data,root.getRight(),result);
        }
    }

    /**
     * 实现非递归前序遍历(根左右)
     * 实现思想：
     * 利用栈的先进后出的特性，在遍历每一个节点的时候将其存入栈中
     * 当需要返回上一层的时候从栈中弹出即可
     * @param root 根节点
     */
    private List<Integer> fBeforeTraverse(Node root) {
        Node cur = root;
        if(cur==null)  return null;
        List<Integer> result = new ArrayList<>();
        //通过栈来辅助进行树的前序遍历
        Stack<Node> stack = new Stack<>();
        while(true) {
            while(cur != null) {
                result.add(cur.getData());
                stack.push(cur);
                cur = cur.getLeft();
            }
            if(stack.isEmpty()) break;
            cur = stack.pop();
            cur = cur.getRight();
        }
        return result;
    }



    /**
     * 非递归中序遍历 （左根右）
     * @param root 根节点
     * @return
     */
    private Integer[] fMiddleTraverse(Node root) {
        Node first = root;
        if(first==null)  return null;
        Integer[] result = new Integer[size];
        int index = 0;
        Stack<Node> S = new Stack<>();
        while(true) {
            while(first!=null) {
                S.push(first);
                first = first.getLeft();
            }
            if(S.isEmpty()) break;
            first = S.pop();
            result[index++] = first.getData();
            first = first.getRight();
        }
        return result;
    }



    /**
     * 后序遍历非递归版（左右根）
     * @param root 根节点
     * @return
     */
    private Integer[] fAfterTraverse(Node root) {
        Node first = root;
        Integer[] result = new Integer[size];
        int index = 0;
        if(first==null)  return null;
        Stack<Node> S = new Stack<>();
        Stack<Node> Sed = new Stack<>();
        do {
            while (first != null && !S.contains(first)) {
                S.push(first);
                first = first.getLeft();
            }
            first = S.pop();
            Sed.push(first);
            result[index++] = first.getData();
            if (!S.isEmpty()) first = S.peek();
            if (first.getRight() != null && !Sed.contains(first.getRight())) {
                first = first.getRight();
            }
        } while (!S.isEmpty());
        Sed.clear();
        return result;
    }

    /**
     * 将层次遍历的结果存入二维数组中(层次遍历用到的辅助数据结构是队列)
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        Queue<Node> queue= new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if(root!=null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++) {
                Node node = queue.poll();
                assert node != null;
                temp.add(node.getData());
                if(node.getLeft()!=null) queue.add(node.getLeft());
                if(node.getRight()!=null) queue.add(node.getRight());
            }
            result.add(temp);
        }
        return result;
    }

    /**
     * 根据前序，中序遍历数组重建树
     * @param preOrder
     * @param inOrder
     * @return
     */
    Node buildTree(int[] preOrder,int[] inOrder) {
        if(preOrder.length==0) return null;
        Node root = new Node(preOrder[0]);
        if(preOrder.length==1) return root;
        int index = 0;
        for(int i=0;i<inOrder.length;i++) {
            if(preOrder[0]==inOrder[i]) {
                index = i;
                break;
            }
        }
        int[] leftPreorder = new int[index];
        int[] leftInorder = new int[index];
        int[] rightPreorder = new int[inOrder.length-index-1];
        int[] rightInorder = new int[inOrder.length-index-1];

        for(int i=0;i<index;i++) {
            leftPreorder[i] = preOrder[i+1];
            leftInorder[i] = inOrder[i];
        }

        for(int i=0;i<inOrder.length-index-1;i++) {
            rightInorder[i] = inOrder[index+1+i];
            rightPreorder[i] = preOrder[index+1+i];
        }

        root.left = buildTree(leftPreorder,leftInorder);
        root.right = buildTree(rightPreorder,rightInorder);
        return root;
    }


    /**
     * 重建二叉树
     * @param preOrder
     * @param inOrder
     */
    void buildBinaryTree(int[] preOrder,int[] inOrder) {
        root = buildTree(preOrder,inOrder);
    }


}
